﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TreeNode<T>
{
    private T element;
    private TreeNode<T> prev;
    private TreeNode<T> next;

    public TreeNode(T element)
    {
        this.element = element;
        prev = null;
        next = null;
    }

    public TreeNode()
    {
        this.element = default(T);
        prev = null;
        next = null;
    }

    public T Element
    {
        get
        {
            return element;
        }
        set
        {
            element = value;
        }
    }

    public TreeNode<T> Prev
    {
        get
        {
            return prev;
        }
        set
        {
            prev = value;
        }
    }

    public TreeNode<T> Next
    {
        get
        {
            return next;
        }
        set
        {
            next = value;
        }
    }   
}

public struct Tree<T>where T:IComparable<T>
{
    private TreeNode<T> root;

    public Tree(T e)
    {
        root = new TreeNode<T>(e);
    }

    private void AddNode(T elToAdd, TreeNode<T> node, int dir)
    {

        int res;
        res = node.Element.CompareTo(elToAdd);

        if (res < 0 && dir < 0)
        {
            TreeNode<T> newNode = new TreeNode<T>(node.Element);
            newNode.Next = node.Next;
            newNode.Prev = node.Prev;
            node.Next = null;
            node.Prev = newNode;    
        }
        else if (res > 0 && dir > 0)
        {
            TreeNode<T> newNode = new TreeNode<T>(node.Element);
            newNode.Next = node.Next;
            newNode.Prev = node.Prev;
            node.Prev = null;
            node.Next = newNode;
        }
        else if (res > 0)
        {
            if (node.Prev != null)
                AddNode(elToAdd, node.Prev, -1);
            else
            {
                TreeNode<T> newNode = new TreeNode<T>(elToAdd);
                node.Prev = newNode;
            }
        }
        else if (res < 0)
        {
            if (node.Next != null)
                AddNode(elToAdd, node.Next, 1);
            else
            {
                TreeNode<T> newNode = new TreeNode<T>(elToAdd);
                node.Next = newNode;
            }
        }
        else
        {
            TreeNode<T> newNode = new TreeNode<T>(elToAdd);
            TreeNode<T> temp = node.Next;
            node.Next = newNode;
            newNode.Next = temp;
        }
    }

    public void Add(T elToAdd)
    {
        AddNode(elToAdd, root, 0);       
    }


}
